package huawei;

/**
 * 构造三叉树
 */
public class Create3Tree {


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode middle;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    public static void main(String[] args) {
        int[] ints = {5000, 2000, 5000, 8000, 18000};

        if (ints == null || ints.length == 0) {
            System.out.println(0);
        }

        TreeNode root = new TreeNode(ints[0]);
        Create3Tree create3Tree = new Create3Tree();
        for (int i = 1; i < ints.length; i++) {
            create3Tree.buildTree(root, ints[i]);
        }


        System.out.println(create3Tree.computeHigh(root));
    }

    // 计算树的高度
    public int computeHigh(TreeNode node) {
        if (node == null) {return 0;}

        int lh = computeHigh(node.left);
        int mh = computeHigh(node.middle);
        int rh = computeHigh(node.right);

        return Math.max(lh, Math.max(mh, rh)) + 1;
    }

    public void buildTree(TreeNode node, int num) {
        if (num < node.val - 500) {
            // 插入左节点中
            if (node.left == null) {
                node.left = new TreeNode(num);
            } else {
                buildTree(node.left, num);
            }
        } else if (num > node.val + 500) {
            // 插入右边
            if (node.right == null) {
                node.right = new TreeNode(num);
            } else {
                buildTree(node.right, num);
            }
        } else {
            // 插入中间
            if (node.middle == null) {
                node.middle = new TreeNode(num);
            } else {
                buildTree(node.middle, num);
            }
        }
    }
}
